package GreedyAlgorithm;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 用最少数量的箭引爆气球  https://leetcode-cn.com/leetbook/read/greedy/rvwe8r/
 */
public class Code04 {

    public int findMinArrowShots(int[][] points) {

        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] > o2[1])
                    return 1;
                else
                    return -1;
            }
        });

        System.out.println(Arrays.deepToString(points));

        // 数组排序
        int ans = 0;
        for (int i = 0; i < points.length; i++) {
            if (i == points.length-1)
                ans++;
            for (int j = i+1; j < points.length; j++) {

                if (points[i][1] < points[j][0]){
                    i=j-1;
                    ans++;
                    break;
                }
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        Code04 code04 = new Code04();
        System.out.println("code04.findMinArrowShots(new int[][]{{1,2},{3,4},{5,6},{7,8}}) = " + code04.findMinArrowShots(new int[][]{{1,2},{1,2}}));
    }
}
